package com.xzz.tree;

/**
 * @author: hhz
 * @create: 2021-12-22 15:51
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 **/
public class CountNodes {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        System.out.println(countNodes(node1));

    }

    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //因为是完全二叉树 所以左右子树 必然有一颗是满二叉树
        int leftLen = 1;
        TreeNode left = root;
        while (left.left!=null){
            leftLen++;
            left = left.left;
        }

        int rightLen = 1;
        TreeNode right = root;
        while (left.right!=null){
            rightLen++;
            right = right.right;
        }
        if(leftLen == rightLen){
            //满二叉树的节点=2的n次方-1 n为树的高度
            return (int)Math.pow(2,leftLen)-1;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
